package com.aqie.easy.dynamicProgramming;



/**
 * 121 一次买卖 利润最大
 * 最大利润=max{前一天最大利润, 今天的价格 - 之前最低价格}
 */
public class MaxProfit {
    /**
     * 找两个差值最大数
     * 1, 一次遍历 4ms
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        int last = 0, profit = 0;
        for (int i = 0; i < prices.length - 1; ++i) {
            last = Math.max(0, last + prices[i+1] - prices[i]);
            profit = Math.max(profit, last);
        }
        return profit;
    }

    /**
     * 2, 一次遍历 2ms  DP
     * @param prices
     * @return
     */
    public int maxProfit1(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int price : prices) {
            if (price < minprice)
                minprice = price;
            else if (price - minprice > maxprofit)
                maxprofit = price - minprice;
        }
        return maxprofit;
    }

    /**
     * 记录前面的最小价格，用当天价格减去最小价格 一定是这天最大利润
     * DP 3ms
     * @param prices
     * @return
     */
    public int maxProfit11(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int res = 0;
        int pre_min = prices[0];
        for (int i = 1; i < prices.length; i++){
            res = Math.max(res, prices[i] - pre_min);
            pre_min = Math.min(pre_min, prices[i]);
        }
        return res;

    }


    /**
     * 3, 三路快排 3ms
     * @param prices
     * @return
     */
    public int maxProfit2(int[] prices) {
        if(prices==null||prices.length==1)
            return 0;
        int len=prices.length;
        int money=0,maxIndex=0,minIndex=0;
        for(int index=1;index<len;index++){
            if(prices[index]<prices[minIndex]){
                maxIndex=index;
                minIndex=index;
            }
            else if(prices[index]>prices[maxIndex]) {
                maxIndex=index;
                money= Math.max(money,prices[maxIndex]-prices[minIndex]);
            }
        }
        return money;
    }

    /**
     * 4. 暴力法 292ms
     * @param prices
     * @return
     */
    public static int maxProfit3(int[] prices) {
        int ans = 0;
        for (int i = 0; i < prices.length; i++){
            for (int j = i + 1; j < prices.length; j++){
                ans = Math.max(ans, prices[j] - prices[i]);
            }
        }
        return ans;
    }





    public static void main(String[] args) {
        // int[] prices = {7,1,5,3,6,4};
        int[] prices = {7,6,4,3,1};
        System.out.println(maxProfit3(prices));
    }
}
